The present invention relates to the field of semiconductor memory; more specifically, it relates to content addressable memory (CAM), in which data is accessed and modified based upon the content of the stored data.
A CAM device permits the contents of memory to be searched and matched without having to specify specific memory cell addresses in order to retrieve the data stored in the memory. To search a CAM device, every bit of each word in the memory is compared simultaneously with data placed in a compare register. If there is a match of every bit in a particular memory location with every bit of data in the compare register a match signal is asserted on a matchline. The match signals from every word are used to generate the address of the matching data in the CAM. CAM devices are useful because they have very fast search times compared to search times of normal random access memory (RAM) whether the RAM is a dynamic random access memory (DRAM) type or a static random access memory (SRAM) type.
Turning to FIG. 1, FIG. 1 is a block diagram of a related art CAM device. CAM device 100 comprises a plurality of CAM cells 105, each coupled to a wordline 110. An input of each CAM cell 105 is also coupled to a pair of bitlines 115 and a compare output of each CAM cell is coupled to the gate of an n-type field-effect transistor (NFET) 120. The drain of each NFET 120 is coupled to a matchline 125 and the source of each NFET 120 is coupled to ground. Matchline 125 is precharged high by a p-type field-effect transistor (PFET) 130 in response to a search enable signal (SE) applied to the gate of PMET 130. Data is written and read out of CAM cells 105 through bitline pairs 115. In a CAM array, which contains a plurality of CAM devices 100, a wordline signal applied to wordline 110 controls which CAM cells 105 data is written to or read from.
When CAM device 100 is idle, search enable is held low, causing matchline 125 to precharge high. In a search operation, search enable is brought high releasing the precharge. If the data bit stored in a particular CAM cell 105 does not match the compare bit on the corresponding bitline pair 115 for the CAM cell then the corresponding NFET 120 is turned on and the matchline is discharged to ground thereby causing matchline 125 to go low. A high on matchline 125 indicates a match; a low indicates not a match.
FIG. 2 i s a circuit diagram of the related art CAM device of FIG. 1. In FIG. 2, CAM cells 105 are SRAM cells. Each bitline pair 115 is comprised of a bitline 135A and a bitline not 135B. Each CAM cell 105 comprises NFETs 140A, 140B, 150A and 150B. Each CAM cell 105 further comprises inverters 145A and 145B. The gate s of NFETs 140A and 140B are coupled to wordline 110. The source of NFET 140A is coupled to bitline 135A The drain of the NFET 140A is coupled to the input of inverter 145A, the output of inverter 145B and the gate of NFET 120B. The source of NFET 140B is coupled to bitline not 135B. The drain of NFET 140B is coupled to the input of inverter 145B, the output of inverter 145A and the gate of NFET 150A. The source of NFET 150A is coupled to bitline 135A. The source of NFET 150B is coupled to bitline not 135B. The drains of NFETs 150A and 150B are tied together and to the gate of NFET 120. The drain of NFET 120 is coupled to matchline 125 and the source of NFET 120 is coupled to ground. The source of PFET 130 is tied to VDD and the drain of PFET 130 is coupled to matchline 125. The gate of PFET 130 is coupled to SE. NFETs 140A, 140B, and inverters 145A and 145B comprise memory cell 152, which, in this example, is a SRAM cell. NFETs 150A and 150B comprise a compare cell 154, that outputs a low on a match.
In a search operation, wordline 110 is held low and matchline 125 is pre-charged high. If bitline 135A is high (bitline not 135B is low) and the output of inverter 145A is low (the output of inverter 145B is high) then NFET 150A is off, NFET 150B is on, NFET 120 is off and matchline 125 stays high indicating a match. If bitline 135A is high (bitline not 135B is low) and the output of inverter 145A is high (the output of inverter 145B is low) then NFET 150A is on, NFET 150B is off, NFET 120 is on and matchline 125 goes low indicating not a match. If bitline 135A is low (bitline not 135B is high) and the output of inverter 145A is high (the output of inverter 145B is low) then NFET 150A is on, NFET 150B is off, NFET 120 is off and matchline 125 stays high indicating a match. If bitline 135A is low (bitline not 135B is high) and the output of inverter 145A is low (inverter 145B is high) then NFET 150A is off, NFET 150B is on, NFET 120 is on and matchline 125 goes low indicating not a match.
Since there is a 50% probability of a discharge due to a mismatch on any single bit, the probability of discharging matchline 125, and then having to pre-charge again exceeds 99% when the word-length is eight or greater. This leads to high power consumption, a significant problem in devices designed for low power use. A second problem, is even with advanced CMOS technology, with very long word-lengths it is difficult to distinguish between a single NFET 120 turning on and the leakage of all NFETs 120 together in CAM device 100 leading to false compares.
A first aspect of the present invention is a content addressable memory device comprising: a NAND-NOR chain comprised an alternating sequence of NAND and NOR stages; the NAND stages, each including a first CAM cell comprising a first memory cell that stores a first data bit and a first compare cell that compares the first data bit with a first compare bit and generates a first compare signal indicating whether the first data bit matches the first compare bit and a logical NAND gate that combines the first compare signals of other first CAM cells in the NAND stage; the NOR stages, each including a second CAM cell comprising a second memory cell that stores a second data bit and a second compare cell that compares the second data bit with a second compare bit and generates a second compare signal indicating whether the second data bit matches the second compare bit and a logical NOR gate that combines the second compare signals of other second CAM cells in the NOR stage; and the NAND-NOR chain generating a match signal indicating a match of all the compare bits to all the data bits in the content addressable memory device.
A second aspect of the present invention is a content addressable memory device, comprising: a NAND-NOR chain comprising an alternating sequence of NAND and NOR stages; the NAND stages, each including a first CAM cell comprising a first memory cell that stores a first data bit and a first compare cell that compares the first data bit with a first compare bit and generates a first compare signal indicating whether the first data bit matches the first compare bit and a logical NAND gate that combines the first compare signals of other first CAM cells in the NAND stage, the output of the NAND gate going low in response to all data bits matching all compare bits in the NAND stage; the NOR stages, each including a second CAM cell comprising a second memory cell that stores a second data bit and a second compare cell that compares the second data bit with a second compare bit and generates a second compare signal indicating whether the second data bit matches the second compare bit and a logical NOR gate that combines the second compare signals of other second CAM cells in the NOR stage, the output of the NOR gate going high in response to all data bits matching all compare bits in the NOR stage; and the NAND-NOR chain generating a match signal, the match signal being high in response to a match of all the compare bits to all the data bits in the content addressable memory device.